class Solution {
    /*  
        思路一：递归遍历
        分解为子问题：对于每两个个节点比较，如果其中一个为null，则不对称
        如果两个都为null，则对称
        如果两个都不为null，则比较他们的子树（A的左节点和B的右节点比较）
        空间复杂度：O(N)，栈的深度，也就是树的高度
    */
    public boolean isSymmetric(TreeNode root) {
        return seek(root,root);
    }
    public boolean seek(TreeNode p1,TreeNode p2){ 
        if(p1==null && p2==null) // 两个空节点
            return true;
        if(p1==null || p2==null) // 仅有一个空节点
            return false;
        /*
            两个非空对称相同必须满足3个条件: 值相等，p1的左节点和p2的右节点对称
        */ 
        return p1.val == p2.val && seek(p1.left,p2.right) && seek(p1.right,p2.left);
    }
}
class Solution {
    /*
        思路2：每次提取两个节点，并比较他们的值（两个连续节点的值应该是相同的），然后把两个节点的左右儿
        相反顺序插入
    */
    public boolean isSymmetric(TreeNode root) {
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        q.offer(root);
        while( !q.isEmpty() ){
            TreeNode p1 = q.poll();
            TreeNode p2 = q.poll(); // 每次取出队列的两个点
            
            if(p1==null && p2==null)// 空节点，就不能插入儿子节点了
                continue;
            if(p1==null || p2==null || p1.val!=p2.val) 
                return false;
                
            /*
                由于每次取出的是相邻的节点，所以先插入p1在插入p2
            */
            q.offer(p1.left);
            q.offer(p2.right);
            
            q.offer(p1.right);
            q.offer(p2.left);
        }
        return true;
    }
}